"""
509. 斐波那契数
https://leetcode.cn/problems/fibonacci-number/description/?envType=study-plan-v2&envId=dynamic-programming
F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)
"""
class Solution:
    def fib(self, n: int) -> int:
        if n == 1:
            return 1
        p = 0
        q = 1
        r = 0
        for i in range(n-1):
            r = p + q
            p = q
            q = r 
        return r

print(Solution().fib(2)) #1
print(Solution().fib(3)) #2
print(Solution().fib(4)) #3
